var arr = [];

for (var i = 0; i < 10000 ; i++) {
	arr[i] = Math.floor(Math.random() * 10000)
}

function Node(value) {
	this.value = value;
	this.left = null;
	this.right = null;
}

var num = 0;
function search(arr, target) {
	for (var i = 0; i < arr.length; i ++) {
		num += 1;
		if(arr[i] === target) return true
	}
	return false
}

function addNode(root, num) {
	if(root === null) return ;      //根节点为空
	if(root.value === num) return;   // 已存在
	if(root.value < num) {      //根节点 < 目标节点
		if(root.right === null) root.right = new Node(num);     //如果右侧为空，添加节点
		else addNode(root.right, num)                   //右侧不为空，向右侧递归
	} else {                    //根节点 > 目标节点
		if(root.left === null) root.left = new Node(num);        //如果左侧为空，添加节点
		else addNode(root.left, num)                //左侧不为空 向左侧递归
	}
}

function buildSearchTree(arr) {
	if(arr === null || arr.length ===0) return null
	var root = new Node(arr[0])
	for(var i = 1; i <arr.length; i++) {
		addNode(root, arr[i])
	}
	return root
}

var num2 = 0
function searchByTree(root, target) {
	if(root === null) return false;
	num2 += 1;
	if(root.value === target) return true;
	if(root.value > target) return searchByTree(root.left, target)
	else return searchByTree(root.right, target)
}

console.log(search(arr, 1000))
console.log('暴力方法：' + num)


var root = new buildSearchTree(arr)
// console.log(root)

console.log(searchByTree(root, 1000))
console.log('二叉搜索树的次数：' + num2)

